import java.util.Arrays;
import java.util.Objects;

public class MyHeap {

        int[] elm;
        int usedSize;
        public MyHeap(){
            elm=new int[10];
        }
        public void shiftDown(int parent,int len){
            //parent记录每棵树的根节点，len记录每棵树的调整的结束位置
            int child=2*parent+1;//根据父节点的位置确定左子节点的位置（完全二叉树为有一个左孩子或者一左一右两个孩子）
            //向下转型的时候，由大到小，孩子的下标为增加边界条件为len
            while(child<len){
                //判断是否有右孩子并确定两个孩子中的最大值
                if(child+1<len&&elm[child]<elm[child+1]){
                    child++;
                }
                if(elm[child]>elm[parent]){
                    //建立为大根对，父节点值大于子节点
                    int tmp=elm[child];
                    elm[child]=elm[parent];
                    elm[parent]=tmp;
                    //赋值下一棵树，并找到根节点和左子树
                    parent=child;
                    child=2*parent+1;
                }else {
                    //如果本来就是大根树直接返回
                    break;
                }
            }
        }
        public void creatHeap(int[] array){
            //将数组的值拷贝到堆的底层数组当中
            for (int i = 0; i < array.length; i++) {
                elm[i]=array[i];
                usedSize++;
            }
            for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
                //调整根节点，从下往上，依次进行遍历。
                shiftDown(parent,usedSize);
            }
        }
        public void offer(int val){
            if(isFull()){
                elm= Arrays.copyOf(elm,2*elm.length);
            }
            elm[usedSize++]=val;
            //注意这里传入的是usedSize-1
            shiftUp(usedSize-1);
        }
        private void shiftUp(int child){
            //末尾节点的父节点
            int parent=(child-1)/2;
            while (child>0){
                //当父亲节点小于子节点时交换，即大根堆
            if(elm[parent]<elm[child]){
                int tmp=elm[parent];
                elm[parent]=elm[child];
                elm[child]=tmp;
                //如果为左右子树可判断两个子树，也可循环进行判断
                parent=(child-1)/2;
            }else {
                break;
            }
            }

        }
        public boolean isFull(){
            return usedSize==elm.length;
        }
        public boolean isEmpty(){
            return usedSize==0;
        }
        public int pull(){
            if(isEmpty()){
                throw new RuntimeException("优先级队列为空");
            }
            int tmp=elm[0];
            elm[0]=elm[usedSize-1];
            elm[usedSize-1]=tmp;
            usedSize--;
            shiftDown(0,usedSize);
            return tmp;
        }
        public int peek(){
            if(isEmpty()){
                throw new RuntimeException("优先级队列为空");
            }
            return elm[0];
        }
        public void heatSort(){
            int end=usedSize-1;
            while(end>0){
                int tmp=elm[0];
                elm[0]=elm[end];
                elm[end]=tmp;
                shiftDown(0,end);
                end--;
            }
        }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyHeap myHeap = (MyHeap) o;
        return usedSize == myHeap.usedSize && Arrays.equals(elm, myHeap.elm);
    }

    @Override
    public int hashCode() {
        int result = Objects.hash(usedSize);
        result = 31 * result + Arrays.hashCode(elm);
        return result;
    }
}
